package offer.offer02;

import java.util.ArrayList;
import java.util.List;

/**
 * 10, 100, 主要是复制路径消耗了很多时间
 * 基础的dfs, 是叶子节点的时候做一个判断
 * 注意, 必须是叶子节点
 * ArrayList变为LinkedList之后变慢了很多
 *
 * 回溯吧, 记得List的函数。l.add(x), l.remove(l.size());
 */
public class Solution34 {
    private List<List<Integer>> retList = new ArrayList<>();
    private int target;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        long time1 = System.currentTimeMillis();
        if(root == null) return retList;
        target = sum;
        List<Integer> rootList = new ArrayList<>();
//        retList.add(rootList);
        rootList.add(root.val);
        achieved(root, rootList, root.val);
        long time2 = System.currentTimeMillis();
        System.out.println("用时: " + (time2 - time1));
        return retList;
    }

    public void achieved(TreeNode node, List<Integer> route, int curSum){
        if(node.left != null) {
            List<Integer> leftList = new ArrayList<>(route);
            leftList.add(node.left.val);
            achieved(node.left, leftList, curSum + node.left.val);
        }
        if(node.right != null) {
            List<Integer> rightList = new ArrayList<>(route);
            rightList.add(node.right.val);
            achieved(node.right, rightList, curSum + node.right.val);
        }
        if(node.left == null && node.right == null){
            if(curSum == target) retList.add(route);
        }

    }

    public static void main(String[] args) {
        TreeNode input = new TreeNode(5);
        input.left = new TreeNode(4);
        input.right = new TreeNode(8);
        input.left.left = new TreeNode(15);
        input.right.left = new TreeNode(13);
        input.right.right = new TreeNode(4);
        input.left.left.left = new TreeNode(7);
        input.left.left.right = new TreeNode(-2);
        input.right.right.left = new TreeNode(5);
        input.right.right.right = new TreeNode(1);

        List<List<Integer>> output = new Solution34().pathSum(input, 22);
        for(List<Integer> l: output){
            System.out.println(l);
        }
    }
}
